package org.example.myleet.rosalind.rear;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        String input = "1 2 3 4 5 6 7 8 9 10\n" +
//                "3 1 5 2 7 4 9 6 10 8\n" +
//                "\n" +
//                "3 10 8 2 5 4 7 1 6 9\n" +
//                "5 2 3 1 7 4 10 8 6 9\n" +
//                "\n" +
//                "8 6 7 9 4 1 3 10 2 5\n" +
//                "8 2 7 6 9 1 5 3 10 4\n" +
//                "\n" +
//                "3 9 10 4 1 8 6 7 5 2\n" +
//                "2 9 8 5 1 7 3 4 6 10\n" +
//                "\n" +
//                "1 2 3 4 5 6 7 8 9 10\n" +
//                "1 2 3 4 5 6 7 8 9 10\n";
        String input = "4 2 7 3 6 8 10 5 1 9\n" +
                "7 4 6 2 10 3 1 8 9 5\n" +
                "\n" +
                "4 8 1 2 6 7 3 10 5 9\n" +
                "6 7 8 3 9 2 10 5 4 1\n" +
                "\n" +
                "3 9 5 4 10 1 2 8 6 7\n" +
                "7 2 3 8 5 1 6 9 10 4\n" +
                "\n" +
                "8 2 7 10 6 1 3 9 4 5\n" +
                "9 7 4 10 8 6 2 5 3 1\n" +
                "\n" +
                "8 1 9 3 4 10 2 6 7 5\n" +
                "3 7 6 4 8 1 9 2 5 10\n";
        String[] lines = input.split("\n");
        for (int i = 0; i < lines.length; ++i) {
            String line1 = lines[i];
            if (line1.length() < 1) {
                continue;
            }
            int[] pi = parseStringToArr(line1);
            ++i;
            String line2 = lines[i];
            int[] sigma = parseStringToArr(line2);
            solution.findReversalDistance(pi.length, pi, sigma);
        }
    }

    private static int[] parseStringToArr(String line) {
        String[] parts = line.split(" ");
        int[] arr = new int[parts.length];
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = Integer.parseInt(parts[i]);
        }
        return arr;
    }

    public void findReversalDistance(int n, int[] pi, int[] sigma) {
        if (isSame(pi, sigma)) {
            System.out.print("0 ");
            return;
        }
        //记忆化搜索
        Map<String, Integer> memo1 = new HashMap<>();
        //from pi to sigma
        Queue<int[]> queue = new LinkedList<>();
        int[] arr = copyArr(pi);
        queue.add(arr);
        memo1.putIfAbsent(arrToString(arr), 0);
        while (!queue.isEmpty()) {
            //BFS方式，将每一步产生的子数组翻转结果用于下一步搜索
            //从队列中弹出下一步
            arr = queue.poll();
            //从记忆中找到上一步的翻转次数
            Integer reversalCount = memo1.get(arrToString(arr));
            ++reversalCount;
            for (int l = 1; l < n; ++l) {
                for (int s = 0; s + l < n; ++s) {
                    //产生下一步
                    int[] newArr = copyArr(arr);
                    reverse(newArr, s, s + l);
                    if (isSame(sigma, newArr)) {
                        //找到，直接退出
                        System.out.printf("%d ", reversalCount);
                        return;
                    }
                    String newArrStr = arrToString(newArr);
                    if (!memo1.containsKey(newArrStr)) {
                        memo1.put(newArrStr, reversalCount);
                        if (reversalCount < 5) {
                            //！注意，参考高手的解法中使用了双向搜索的技巧，将45^10复杂度降到45^5使暴力BFS变成可能
                            queue.add(newArr);
                        }
                    }
                }
            }
        }
        //try from sigma to pi
        //反向做一样的搜索
        int ans = 1000;
        Map<String, Integer> memo2 = new HashMap<>();
        arr = copyArr(sigma);
        queue.add(arr);
        memo2.putIfAbsent(arrToString(arr), 0);
        while (!queue.isEmpty()) {
            arr = queue.poll();
            Integer reversalCount = memo2.get(arrToString(arr));
            ++reversalCount;
            for (int l = 1; l < n; ++l) {
                for (int s = 0; s + l < n; ++s) {
                    int[] newArr = copyArr(arr);
                    reverse(newArr, s, s + l);
                    if (isSame(pi, newArr)) {
                        //找到了，也可以结束
                        System.out.printf("%d ", reversalCount);
                        return;
                    }
                    String newArrStr = arrToString(newArr);
                    Integer fromPi = memo1.get(newArrStr);
                    if (null != fromPi) {
                        //反向搜索中遇到正向搜寻的路径，打通了其中一条翻转的路径，但不知道是不是最优的，先记录下来
                        ans = Math.min(ans, fromPi + reversalCount);
                    }
                    if (!memo2.containsKey(newArrStr)) {
                        memo2.put(newArrStr, reversalCount);
                        if (reversalCount < 4) {
                            queue.add(newArr);
                        }
                    }
                }
            }
        }
        System.out.printf("%d ", ans);
    }

    private String arrToString(int[] arr) {
        StringBuilder sb = new StringBuilder(arr.length * 2);
        for (int i = 0; i < arr.length; ++i) {
            sb.append(arr[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    private int[] copyArr(int[] arr) {
        int[] copy = new int[arr.length];
        System.arraycopy(arr, 0, copy, 0, arr.length);
        return copy;
    }

    private boolean isSame(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; ++i) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Reverse an interval of an array, include start and end
     * @param arr array
     * @param start include
     * @param end include
     * @return Reverse the interval from start to end on the original array
     */
    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int t = arr[start];
            arr[start] = arr[end];
            arr[end] = t;
            ++start;
            --end;
        }
    }
}
